#include <cstring>
#include <algorithm>
#include <iostream>

#ifndef VECTOR_H
#define VECTOR_H

/**
 * @brief 类模板 Vector
 * 
 * @tparam T 
 */
template <typename T> class Vector
{
    private:
        int iCapacity;
        int iElementNumber;
        T* tElements;
        void reserve(const int &);
    
    public:
        /**
         * @brief 构造函数，生成一个给定元素数量的Vector
         * 
         * @param n 
         */
        Vector(int n = 0): iCapacity(n + SPARE_CAPACITY), iElementNumber(n)
        {
            tElements = new T [iCapacity];
        }

        /**
         * @brief 构造函数，根据已有Vector进行深拷贝，生成一个Vector
         * 
         * @param rhs 
         */
        Vector(const Vector &rhs): iCapacity(rhs.iCapacity), iElementNumber(rhs.iElementNumber)
        {
            tElements = new T [iCapacity];
            std::memcpy(tElements, rhs.tElements, sizeof(T) * iCapacity);
        }

        ~Vector()
        {
            if(iCapacity) delete [] tElements;
            iCapacity = iElementNumber = 0;
        }

        Vector & operator = (const Vector &);
        void resize(const int &);
        void reverse();
        T & operator [] (const int &);
        const T & operator [] (const int &) const;
        
        int size() const;
        int capacity() const;
        bool empty() const;
        
        void push_back(const T &);
        void push_back(T &&);
        void pop_back();
        void pop_front();
        const T & back() const;
        
        typedef T* iterator;
        typedef const T* const_iterator;
        iterator begin();
        const_iterator begin() const;
        iterator end();
        const_iterator end() const;

        static const int SPARE_CAPACITY = 16;
};

/**
 * @brief 私有成员函数，用于修改容量。实现时申请一个更大的空间，然后将已有元素拷贝过去，再释放原空间。
 * 
 * @tparam T 
 * @param newCapacity 
 */
template <typename T> void Vector<T>:: reserve(const int & newCapacity)
{
    if(newCapacity < iElementNumber)
        return;
    T* newArray = new T [newCapacity];
    std::memcpy(newArray, tElements, sizeof(T) * iElementNumber);
    T* tmp = tElements;
    tElements = newArray;
    iCapacity = newCapacity;
    delete [] tmp;
}

/**
 * @brief 以右式初始化一个局部Vector，与自身交换，然后原来的元素会进入局部变量，从而利用局部变量的生存周期自然析构
 * 
 * @tparam T 
 * @param rhs 
 * @return Vector<T>& 
 */
template <typename T> Vector<T> & Vector<T>:: operator = (const Vector & rhs)
{
    Vector<T> tmp(rhs);
    std::swap(iCapacity, tmp.iCapacity);
    std::swap(iElementNumber, tmp.iElementNumber);
    std::swap(tElements, tmp.tElements);
    return *this;
}

/**
 * @brief 重设元素数量。调用reserve更新容量，然后重设元素数量。
 * 
 * @tparam T 
 * @param n 
 */
template <typename T> void Vector<T>:: resize(const int & n)
{
    reserve(n);
    iElementNumber = n;
}

/**
 * @brief 翻转内部元素的顺序，直接调用std库内置的reverse
 * 
 * @tparam T 
 */
template <typename T> void Vector<T>:: reverse()
{
    std::reverse(begin(), end());
}

/**
 * @brief 用于访问数组，直接返回数组的第index项
 * 
 * @tparam T 
 * @param index 
 * @return T& 
 */
template <typename T> T & Vector<T>:: operator [] (const int & index)
{
    return tElements[index];
}

/**
 * @brief 用于访问数组，直接返回数组的第index项，作为常量返回，用在右值表达式中提高安全性
 * 
 * @tparam T 
 * @param index 
 * @return T& 
 */
template <typename T> const T & Vector<T>:: operator [] (const int & index) const
{
    return tElements[index];
}

/**
 * @brief 用于查询数组元素数量，注意与容量不同
 * 
 * @tparam T 
 * @return int 
 */
template <typename T> int Vector<T>:: size() const
{
    return iElementNumber;
}

/**
 * @brief 用于查询Vector的实际容量
 * 
 * @tparam T 
 * @return int 
 */
template <typename T> int Vector<T>:: capacity() const
{
    return iCapacity;
}

/**
 * @brief 查询Vector是否没有存储元素
 * 
 * @tparam T 
 * @return true 
 * @return false 
 */
template <typename T> bool Vector<T>:: empty() const
{
    return iElementNumber == 0;
}

/**
 * @brief 用于在Vector尾部添加一个元素。分已满和未满两种情况，已满则调用reserve将容量翻倍
 * 
 * @tparam T 
 * @param x 
 */
template <typename T> void Vector<T>:: push_back(const T & x)
{
    if(iElementNumber == iCapacity)
        reserve(2 * iCapacity + 1);
    tElements[iElementNumber++] = x;
}

/**
 * @brief 用于处理右值引用的push_back
 * 
 * @tparam T 
 * @param x 
 */
template <typename T> void Vector<T>:: push_back(T && x)
{
    if(iElementNumber == iCapacity)
        reserve(2 * iCapacity + 1);
    tElements[iElementNumber++] = x;
}

/**
 * @brief 弹出Vector的最后一个元素。实际实现是假弹出，只把元素数量减一
 * 
 * @tparam T 
 */
template <typename T> void Vector<T>:: pop_back()
{
    --iElementNumber;
}

/**
 * @brief 弹出Vector的第一个元素。实现时，将后面的元素向前拷贝
 * 
 * @tparam T 
 */
template <typename T> void Vector<T>:: pop_front()
{
    --iElementNumber;
    for(int i = 0; i < iElementNumber; i++)
        tElements[i] = tElements[i + 1];
}

/**
 * @brief 访问Vector的尾部元素，不允许修改
 * 
 * @tparam T 
 * @return const T& 
 */
template <typename T> const T & Vector<T>:: back() const
{
    return tElements[iElementNumber - 1];
}

/**
 * @brief 返回迭代器的起始位置
 * 
 * @tparam T 
 * @return Vector<T>::iterator 
 */
template <typename T> typename Vector<T>::iterator Vector<T>:: begin()
{
    return tElements;
}

/**
 * @brief 以常量形式返回迭代器起始位置
 * 
 * @tparam T 
 * @return Vector<T>::const_iterator 
 */
template <typename T> typename Vector<T>::const_iterator Vector<T>:: begin() const
{
    return tElements;
}

/**
 * @brief 返回迭代器的终止位置
 * 
 * @tparam T 
 * @return Vector<T>::iterator 
 */
template <typename T> typename Vector<T>::iterator Vector<T>:: end()
{
    return tElements + iElementNumber;
}

/**
 * @brief 以常量形式返回迭代器的终止位置
 * 
 * @tparam T 
 * @return Vector<T>::const_iterator 
 */
template <typename T> typename Vector<T>::const_iterator Vector<T>:: end() const
{
    return tElements + iElementNumber;
}

/**
 * @brief 重载输出流，用于以流的方式输出Vector
 * 
 * @tparam T 
 * @param out 
 * @param rhs 
 * @return std::ostream& 
 */
template<typename T> std::ostream & operator << (std::ostream & out, const Vector<T> & rhs)
{
    out << "Vector {";
    for(int i = 0; i < rhs.size(); i++)
    {
        if(i == 0) out << rhs[i];
        else out << ", " << rhs[i];
    }
    out << "}";
    return out;
}

#endif